The present invention is related to wireless networks, and in particular to radio plan generation to determine transmit frequencies and transmit powers in a wireless local area network (WLAN).
Radio plan generation for wireless local area networks, including the selection of a frequency channel, sometimes antenna configuration, and a transmit power level for each of a potentially large number of access points (APs), is an integral radio management function of a WLAN system. Current technology successfully manages in the order of 10's of APs, developing the radio plan in a timely fashion. Consider, for example, an IEEE 802.11b network that includes 10 typical access points. Each access point can be assigned to one of three possible channels and one of six possible power levels. Thus each access point has 18 possible configurations. This network would therefore have 1810 or approximately 3.6 trillion possible configurations. An exhaustive search of each possible configuration would take an extremely long time considering that some sort of quality metric must be evaluated for each considered configuration. Thus there is a need in the art for a radio plan generator that can deliver high quality plans, but in a faster and more scalable way than at present.
Furthermore, the number of APs to be managed is likely to grow significantly in the future, as could be the case in the deployment of a high-density enterprise system. It is desirable to have a technique that scales more directly to the number of APs.
Timeliness of frequency assignment is also a strong driver for implementation of dynamic frequency assignment standards, such as the IEEE 802.11h standard, wherein mandated frequency changes can drive reassignment of large groups of APs. This must be done on the fly, with as little impact as possible on network throughput. Speed of reassignment becomes a key factor, especially when a large number of APs is involved.
Radio planning is known for cellular telephones, in particular, for so-called second generation (2G) cellular telephony. Many methods are known for frequency allocation for 2G cellular telephony. See for example, I. Katzela, N. Naghshineh; Channel assignment schemes for cellular mobile telecommunication systems: a comprehensive survey; IEEE Personal Communications (June '96).
See also, U.S. Pat. No. 6,023,459 to Clark et al., and U.S. Pat. No. 6,178,328 to Tang, et al. These methods assign frequency channel, but do not simultaneously assign transmit power.
In 2G cellular telephony, devices in each cell transmit without regard to who is transmitting in other cells. Communication is still reliable as long as the desired signal power is sufficiently far above the total interference power from all the other devices on the same channel. Therefore, in 2G systems, every effort is made to reduce the interference power. As a first step, channels are not reused until distant cells are available for such channels. This can be expressed as a graph coloring problem, where colors represent frequencies, and according to which physically adjacent (or more generally, nearly adjacent) regions have to be colored differently.
WLANs have much smaller cells than 2G systems, and hence achieve much higher per-user data rates. In exchange, WLANs cannot rely on regular cells, nor can the tricks of 2G engineers make up the difference. Walls, windows, doors, partitions, ceilings, and even filing cabinets can lead to anomalous propagation and non-uniform or overlapping cells.
For this and other reasons, WLANs re-define when devices are allowed to transmit. Instead of transmitting without regard to transmissions in other cells, 802.11 WLAN devices determine if the shared wireless medium is quiet and only transmit when this is so.
For example, for 2G systems, a frequency plan with adjacent co-channel APs is fatally poor. Handsets can transmit at the same time, and when they do, they create interference for one another so that the base-station cannot recover their data.
WLANs should ideally minimize the number of interfering devices, especially co-channel APs, that can detect each other, not the total interference power.
In summary, intuitive heuristics, developed from such fields as 2G cellular telephony, may be misleading when applied to WLANs. That is, the closest distance between two co-channel APs is less important than the total number of interfering APs.
Co-assigned above-mentioned incorporated-herein-by-reference U.S. patent application Ser. No. 10/933,102 titled RAPID SEARCH FOR OPTIMAL NETWORK CONFIGURATION provides a search algorithm to find a globally optimal radio plan for a wireless network, including assignments of frequency and transmit power to multiple access points. Two different evaluation metrics are used in order to provide an optimal solution in a reasonable time period. Frequency searches are performed using a special rapid evaluation metric, called the Fast Evaluation Metric (FEM). Given a set of frequency assignment for a set of APs, and path losses between the pairs of APs, the fast evaluation metric (FEM) counts the number of pairs of access points that contend on the same frequency. A lower value indicates a higher quality. Transmit powers are selected using a more refined metric called the Combined Metric (CM) that estimates data throughput. The search results are deterministic and execution time is also substantially deterministic.
The CM has been previously described in above-mentioned incorporated-herein-by-reference U.S. patent application Ser. No. 10/791,466 titled QUALITY EVALUATION FOR WIRELESS COMMUNICATION NETWORKS. The CM considers factors such as contention and collision among access points and client locations, traffic load, the physical space to be covered, etc. The input to the combined metric includes path losses between the access points as well as the frequency and power settings of the access points. The CM requires sufficient computation time that it is not feasible to evaluate it for every possible solution even for a relatively small number of access points.
A first method disclosed in U.S. patent application Ser. No. 10/933,102 includes evaluating the FEM for a first subset of possible frequency assignments to a plurality of access points. The first method further includes, for a plurality of frequency assignments ranked best in FEM, evaluating the CM for all possible assignments of transmit power. The first method further includes identifying a mean transmit power for a plurality of transmit powers ranked best in terms of the evaluated CM. Based on the mean transmit power, the method includes evaluating the FEM for a second subset of possible frequency assignments, the second subset being larger than the first subset; and for a plurality of frequency assignments of this second subset ranked best in FEM, evaluating the CM for all possible assignments of transmit power.
A second method disclosed in U.S. patent application Ser. No. 10/933,102 is a method of assessing communication quality in a wireless network that includes a plurality of access points. The method includes: accepting path loss information indicating path losses among pairs of access points and frequency assignments for the access points, determining for each pair of access points the likelihood of contention based on path loss between the pair and whether they share a common frequency assignment, and counting the number of contending pairs of access points to determine a quality evaluation metric for the wireless network.
A third method disclosed in U.S. patent application Ser. No. 10/933,102 is a method for assigning transmit frequencies and transmit power levels to the APs. The third method includes: applying a first evaluation metric to reduce the solution space of power and frequency assignments and applying a second evaluation metric to find a best set of power and frequency assignments.
In one form, U.S. patent application Ser. No. 10/933,102 discloses a radio planning method that includes a series of sweeps: initial coarse frequency sweep, initial coarse power sweep, final coarse frequency sweep, final coarse power sweep, and final coarse power sweep to determine an optimal radio plan assigning both transmit frequencies and transmit power levels. The initial frequency/power sweep finds a reasonably optimal global AP power setting so that the final frequency/power sweep can concentrate on good frequency plans. A few of the best survivors are taken into a final fine power sweep, with the overall best result being reported to the user.
However, the frequency sweeps include “uniformly sampling” the possible frequency plans and may spend much of their time on poor frequency plans. Moreover there are two coarse power sweeps, and a fine power sweep applied to a few survivor solutions, and these all use the CM which is computationally intense. These aspects mean that there are situations in which the U.S. patent application Ser. No. 10/933,102 method may take minutes or hours to execute, and so it is desired to speed the algorithm up, and/or provide a quick, reasonably optimal, solution, e.g. for demonstration purposes.
Thus there is still a need in the art for a method and system and software to determine a radio plan for a WLAN in a relatively straightforward and rapid fashion. In particular, there is a need for radio planner that uses a direct frequency planner instead of uniformly sampling, so as to spend more time on good frequency plans.
Furthermore, there is a need in the art for a method that provides a good-enough, reasonably optimal radio plan solution that can be presented quickly to users.